package graph;

import linearList.LinkedList;
import linearList.SeqList;
import queue.LinkedQueue;

// 邻接矩阵表示的带权图类
public class MatrixGraph<T> {
    // 最大权值，表示无穷大
    public static final int MAX_WEIGHT = 0x0000ffff;

    private SeqList<T> vertexList;
    private int[][] matrix;

    public static void main(String[] args) {
        testG3();
        testG4();
    }

    private static void testG4() {
        System.out.println("testG4: your code here");
    }

    private static void testG3() {
        System.out.println("testG3: your code here");

    }

    public MatrixGraph(int length) {
        this.vertexList = new SeqList<>(length);
        this.matrix = new int[length][length];
        initEgde();
    }

    public MatrixGraph(T[] vertices, Triple[] edges) {
        this.vertexList = new SeqList<>(vertices);
        this.matrix = new int[vertices.length][vertices.length];
        initEgde();

        for (Triple edge : edges) {
            this.insertEdge(edge);
        }
    }

    private void initEgde() {
        // 不同顶点之间的初始距离为无穷大，顶点和自身的距离为0
        int n = this.vertexList.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    this.matrix[i][j] = MAX_WEIGHT;
                }
            }
        }
    }

    public String toString() {
        String str = this.vertexList.toString() + "，邻接矩阵:  \n";
        int n = this.vertexList.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (this.matrix[i][j] == MAX_WEIGHT)
                    str += "     ∞";
                else str += String.format("%6d", this.matrix[i][j]);
            }
            str += "\n";
        }
        return str;
    }

    // 边 相关操作
    public void insertEdge(int i, int j, int weight) {
        if (i != j) {
            this.matrix[i][j] = weight;
        }
    }

    public void insertEdge(Triple edge) {
        this.insertEdge(edge.row, edge.column, edge.value);
    }

    public void removeEdge(int i, int j) {
        if (i != j) {
            this.matrix[i][j] = MAX_WEIGHT;
        }
    }

    public void removeEdge(Triple edge) {
        this.removeEdge(edge.row, edge.column);
    }

    public int weight(int i, int j) {
        return this.matrix[i][j];
    }

    // 顶点 相关操作
    //返回图的顶点数
    public int vertexCount() {
        return this.vertexList.size();
    }

    //返回顶点vi元素
    public T getVertex(int i) {
        return this.vertexList.get(i);
    }

    //设置顶点vi元素为x
    public void setVertex(int i, T x) {
        this.vertexList.set(i, x);
    }

    //插入元素为x的顶点，返回x顶点序号
    public int insertVertex(T x) {
        int[][] oldMatrix = this.matrix;

        // 添加顶点
        int ret = this.vertexList.insert(x);

        // 初始化邻接矩阵为默认值
        int vertexCount = this.vertexCount();
        this.matrix = new int[vertexCount][vertexCount];
        this.initEgde();

        // 根据之前的邻接矩阵，初始化边
        for (int i = 0; i < vertexCount - 1; i++) {
            for (int j = 0; j < vertexCount - 1; j++) {
                this.matrix[i][j] = oldMatrix[i][j];
            }
        }
        return ret;
    }

    //删除顶点vi及其所有关联的边
    public void removeVertex(int i) {
        int n = this.vertexCount();
        if (i >= 0 && i < n) {
            // 删除顶点
            this.vertexList.remove(i);

            //第i+1～n-1行元素上移一行，n为原顶点数
            for (int j = i + 1; j < n; j++)
                for (int k = 0; k < n; k++)
                    this.matrix[j - 1][k] = this.matrix[j][k];

            //第i+1～n-1列元素左移一列
            for (int k = i + 1; k < n; k++)
                for (int j = 0; j < n; j++)
                    this.matrix[j][k - 1] = this.matrix[j][k];
        } else throw new IndexOutOfBoundsException("i=" + i);
    }

    // 返回顶点vi在vj后的后继邻接顶点序号；
    // 若不存在后继邻接顶点，返回-1。
    private int next(int i, int j) {
        int n = this.vertexList.size();
        if (i >= 0 && i < n) {
            for (int k = j + 1; k < n; k++) {
                if (this.matrix[i][k] > 0 && this.matrix[i][k] < MAX_WEIGHT) {
                    return k;
                }
            }
        }
        return -1;
    }

    // 返回顶点vi的第一个邻接顶点序号
    // 若不存在，返回-1。
    private int first(int i) {
        int n = this.vertexList.size();
        if (i >= 0 && i < n) {
            for (int k = 0; k < n; k++) {
                if (this.matrix[i][k] > 0 && this.matrix[i][k] < MAX_WEIGHT) {
                    return k;
                }
            }
        }
        return -1;
    }

    //非连通图的一次深度优先搜索遍历, 从顶点Vi出发
    public void DFSTraverse(int i) {
        boolean[] visited = new boolean[this.vertexCount()];
        int j = i;
        do {
            if (!visited[j]) {
                System.out.print("{ ");
                this.depthfs(j, visited);                  //从顶点vj出发的一次深度优先搜索
                System.out.print("} ");
            }
            j = (j + 1) % this.vertexCount();              //在其他连通分量中寻找未被访问顶点
        } while (j != i);
        System.out.println();
    }

    //从顶点vi出发的一次深度优先搜索，遍历一个连通分量；visited指定访问标记数组。递归算法
    private void depthfs(int i, boolean[] visited) {
        System.out.print(this.vertexList.get(i) + " ");
        visited[i] = true;
        // Vi所有邻接节点，深度优先遍历，递归调用
        for (int j = this.first(i); j != -1; j = this.next(i, j)) {
            if (!visited[j]) {
                depthfs(j, visited);
            }
        }
    }

    //非连通图的一次广度优先搜索遍历，从顶点Vi出发
    public void BFSTraverse(int i) {
        boolean[] visited = new boolean[this.vertexList.size()];
        int j = i;
        do {
            if (!visited[j]) {
                System.out.print("{ ");
                bfsTraverse(j, visited);                     //从vj出发的一次广度优先搜索
                System.out.print("} ");
            }
            j = (j + 1) % this.vertexCount();                //在其他连通分量中寻找未被访问顶点
        } while (j != i);
        System.out.println();
    }

    //从顶点vi出发的一次广度优先搜索，遍历一个连通分量，使用队列
    private void bfsTraverse(int i, boolean[] visited) {
        System.out.println("bfsTraverse: your code here");
    }

    //Prim算法，构造带权无向图的最小生成树，输出最小生成树的各边及代价
    //mst数组：表示从TV到V-TV的一条边
    public void minSpanTree() {
        // 初始化MST数组。从顶点v0出发，到其它点的权值
        Triple[] mst = new Triple[vertexCount() - 1];
        for (int i = 0; i < mst.length; i++) {
            mst[i] = new Triple(0, i + 1, this.weight(0, i + 1));
        }

        //选择n-1条边，每趟确定一条权值最小的边。
        //MST数组: 0~i是已加入到最小生成树的边TE，i+1~n-1是TV距离V-TV的最小权值
        for (int i = 0; i < mst.length; i++) {
            System.out.print("mst边集合：");
            for (int j = 0; j < mst.length; j++) {
                System.out.print(mst[j].toString() + ",");
            }
            System.out.println();

            //找到最小权值边的下标
            int min = i;
            for (int j = i + 1; j < mst.length; j++) {
                if (mst[j].value < mst[min].value) {
                    min = j;
                }
            }

            //将权值最小的边交换到第i个元素，表示该边加入TE集合
            Triple edge = mst[min];
            if (min != i) {
                mst[min] = mst[i];
                mst[i] = edge;
            }

            //将i+1～n-1的其他边用权值更小的边替换，即TV距离V-TV的最小权值
            int tv = edge.column;                          //刚并入TV的顶点
            for (int j = i + 1; j < mst.length; j++) {
                int v = mst[j].column;                     //原边在V-TV中的终点
                int weight = this.weight(tv, v);
                if (weight < mst[j].value)                   //若(tv,v)边比第j条边的权值更小，则替换
                    mst[j] = new Triple(tv, v, weight);
            }
        }

        // 打印结果
        System.out.print("\n最小生成树的边集合：");
        int mincost = 0;
        for (int i = 0; i < mst.length; i++) {
            System.out.print(mst[i] + " ");
            mincost += mst[i].value;
        }
        System.out.println("，最小代价为" + mincost);
    }

    //非负权值的单源最短路径（Dijkstra算法）
    //S：已确定最短路径集合
    //Path：最短路径终点的前一个顶点,如路径{A，D，C，E} 中的C
    //Dist：最短路径长度
    public void dijkstra(int i) {
        int n = this.vertexCount();             //图的顶点数
        boolean[] S = new boolean[n];           //已求出最短路径的顶点集合，初值全为false
        S[i] = true;                            //标记源点vi在集合S中。若i越界，Java抛出序号越界异常
        int[] dist = new int[n];                //最短路径长度
        int[] path = new int[n];                //最短路径终点的前一个顶点

        //初始化dist和path数组
        for (int j = 0; j < n; j++) {
            dist[j] = this.weight(i, j);
            path[j] = (j != i && dist[j] < MAX_WEIGHT) ? i : -1;
        }

        //寻找从vi到vj的最短路径，vj在V-S集合中
        for (int j = (i + 1) % n; j != i; j = (j + 1) % n) {
            //求路径长度最小值及其下标，确定一条最短路径的终点min并入集合S
            int mindist = MAX_WEIGHT, min = 0;
            for (int k = 0; k < n; k++) {
                if (!S[k] && dist[k] < mindist) {
                    mindist = dist[k];
                    min = k;
                }
            }
            //若没有其他最短路径则算法结束； 此语句对非连通图必需
            if (mindist == MAX_WEIGHT) {
                break;
            }
            S[min] = true;

            //调整从vi到V-S中其他顶点的最短路径及长度，更新dist、path
            for (int k = 0; k < n; k++) {
                if (!S[k] && this.weight(min, k) < MAX_WEIGHT
                        && dist[min] + this.weight(min, k) < dist[k]) {
                    dist[k] = dist[min] + this.weight(min, k);
                    path[k] = min;
                }
            }
        }

        System.out.print(this.getVertex(i) + "的单源最短路径：");
        for (int j = 0; j < n; j++)                            //输出顶点vi的单源最短路径
            if (j != i) {
                System.out.print(toPath(path, i, j) + "长度" + (dist[j] == MAX_WEIGHT ? "∞" : dist[j]) + "，");
            }
        System.out.println();
    }

    // 返回path路径数组中从顶点Vi到顶点Vj的一条路径字符串
    private String toPath(int[] path, int i, int j) {
        //路径单链表，记录最短路径经过的各顶点，用于反序
        LinkedList<T> pathLink = new LinkedList<T>();
        pathLink.insert(0, this.getVertex(j));     //终点Vj
        for (int k = path[j]; k != i && k != j && k != -1; k = path[k]) {
            pathLink.insert(0, this.getVertex(k)); //单链表头插入经过的顶点，反序
        }
        pathLink.insert(0, this.getVertex(i));     //起点vi
        return pathLink.toString();
    }

    //求带权图每对顶点间的最短路径及长度，Floyd算法
    public void floyd() {
        int n = this.vertexCount();                          //图的顶点数
        int[][] path = new int[n][n], dist = new int[n][n];     //最短路径及长度矩阵，初值为0
        for (int i = 0; i < n; i++)                            //初始化dist、path矩阵
            for (int j = 0; j < n; j++) {
                int w = this.weight(i, j);
                dist[i][j] = w;                           //dist初值是图的邻接矩阵
                path[i][j] = i != j && w < MAX_WEIGHT ? i : -1;
            }

        //以Vk作为其他路径的中间顶点
        for (int k = 0; k < n; k++) {
            //测试每对从Vi到Vj路径长度是否更短
            for (int i = 0; i < n; i++) {
                if (i != k) {
                    for (int j = 0; j < n; j++) {
                        if (j != k && j != i && dist[i][k] + dist[k][j] < dist[i][j]) {  //若更短，则替换
                            dist[i][j] = dist[i][k] + dist[k][j];
                            path[i][j] = path[k][j];
                        }
                    }
                }
            }
        }

        System.out.println("每对顶点间的最短路径如下：");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                if (i != j)
                    System.out.print(toPath(path[i], i, j) + "长度" + (dist[i][j] == MAX_WEIGHT ? "∞" : dist[i][j]) + "，");
            System.out.println();
        }
    }
}
